package medium

import "strconv"

/*
时间复杂度：O(N)
空间复杂度：O(N)

解: 注意：以后不要老是想到数字可能高低起伏情况太多不好处理；直接通过一个指针从左往右循环找到第一个不是递增的位置
1.首先一个指针从左往右遍历，找到第一个不满足递增的数，然后将前一个数字-1，如果前一个数字-1后小于更前面的数，则将更前面的数-1直到所有数递增
2.从最左边的-1的那个数之后一个位置开始，将后面所有数变成9
*/

func monotoneIncreasingDigits(n int) int {
	s := []byte(strconv.Itoa(n))
	i := 1
	for i < len(s) && s[i] >= s[i-1] {
		i++
	}
	if i < len(s) {
		for i > 0 && s[i] < s[i-1] {
			s[i-1]--
			i--
		}
		for i++; i < len(s); i++ {
			s[i] = '9'
		}
	}
	ans, _ := strconv.Atoi(string(s))
	return ans
}
